/**
 * @file   Heap.h
 * @author xingyifan
 * @date   2021/08/21 15:38:05
 * 
 * @brief  heap sort
 * 
 * 
 */

#ifndef __HEAP__
#define __HEAP__

#include <iostream>
using namespace std;

//获取i节点的父子节点
#define PARENT(i) ((((i) + 1) >> 1) - 1)
#define LEFTCHILD(i) ((((i) + 1) << 1) - 1)
#define RIGHTCHILD(i) (((i) + 1) << 1)

//最大堆：某个节点的值最多和父节点一样大
class Heap
{
private:
    int size;
    const int const_size;
    double *value;

    void shiftdown(int); //降堆，将指定节点逐渐降低到正确位置
    void build();        //建堆，重复降堆，实现最大堆
    
public:
    Heap(int n, double A[]) : const_size(n)
    {
        size = n;
        value = new double[size];
        for (int i = 0; i < n; i++)
        {
            value[i] = A[i];
        }
    }

    void sort();         //优先队列排序

    friend ostream &operator<<(ostream &out, const Heap &heap)
    {
        for (int i = 0; i < heap.size; i++)
        {
            out << heap.value[i] << " ";
        }
        return out;
    }

    ~Heap()
    {
        if (value != nullptr)
        {
            delete[] value;
        }
    }
};

#endif